package 数据结构.链表;

import java.util.HashSet;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-19
 */
public class JZ52两个链表的第一个公共结点 {

    //长度比较法 我们可以分别统计两个链表的长度，然后对于较长的一个链表先走长度之差这么多步，在同步往后遍历
     class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
             int lenA = length(pHead1), lenB = length(pHead2);

             while (lenA != lenB) {
                if (lenA > lenB) {
                    //如果链表A长，那么链表A先走
                    pHead1 = pHead1.next;
                    lenA--;
                } else {
                    //如果链表B长，那么链表B先走
                    pHead2 = pHead2.next;
                    lenB--;
                }
            }

             while (pHead1 != pHead2) {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }

            return pHead1;
        }
        //统计链表的长度
        private int length(ListNode node) {
            int length = 0;
            while (node != null) {
                node = node.next;
                length++;
            }
            return length;
        }
    }

    //双指针法
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while (cur1 != cur2){
            cur1 = cur1 != null ? cur1.next : pHead2;
            cur2 = cur2 != null ? cur2.next : pHead1;
        }
        //无公共点时 为 null
        return cur1;
    }

    //HashSet方法
    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        HashSet<ListNode> set = new HashSet<>();
        while (pHead1 != null){
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null){
            if (set.contains(pHead2))
                return pHead2;
            pHead2 = pHead2.next;
        }
        return  null;
    }

    public static void main(String[] args) {

    }
}
